package app;

import java.util.Stack;

import datastructure.SuffixTree;
import datastructure.SuffixTreeNode;
import datastructure.generator.SuffixTreeGenerator;

public class LongestCommonStringFinder {
	public static void findLongestCommonString(String a,String b){
		SuffixTreeGenerator generator = SuffixTreeGenerator.getInstance();
		SuffixTree oldTree = generator.buildSuffixTree(a);
		SuffixTree newTree = generator.buildSuffixTree(b,oldTree);
		//newTree.printTree();
		System.out.println(newTree.collectDeepestNodeWithMultipleOwners().getValue());
		System.out.println(parseResult(newTree,newTree.collectDeepestNodeWithMultipleOwners()));
	}
	
	private static String parseResult(SuffixTree tree,SuffixTreeNode node){
		Stack<String> stack = new Stack<String>();
		stack.add(node.getValue());
		while(node.getParent()!= tree.getRootNode()){
			node = node.getParent();
			stack.add(node.getValue());
		}
		StringBuilder builder = new StringBuilder();
		while(!stack.isEmpty()){
			builder.append(stack.pop());
		}
		return builder.toString();
	}
	
	public static void main(String[] args){
		findLongestCommonString("axyzbcmnpqrst","ybcmptstyh");
	}
}
